package Javafoundation;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

public class Topo {
    private class ENode {
        int i;
        ENode nextEdge;
    }


    private class VNode {
        char data;
        ENode firstEdge;
    };

    private List<VNode> mVexs;  // 顶点

    public Topo(char[] vexs, char[][] edges) {

        int vlen = vexs.length;
        int elen = edges.length;

        mVexs = new ArrayList<VNode>();
        for (int i = 0; i < vlen; i++)
        {
            VNode vnode = new VNode();
            vnode.data = vexs[i];
            vnode.firstEdge = null;
            mVexs.add(vnode);
        }

        for (int i = 0; i < elen; i++) {
            // 读取边的起始顶点和结束顶点
            char c1 = edges[i][0];
            char c2 = edges[i][1];
            // 读取边的起始顶点和结束顶点
            int p1 = getPosition(edges[i][0]);
            int p2 = getPosition(edges[i][1]);

            // 初始化node1
            ENode node1 = new ENode();
            node1.i = p2;
            // 将node1链接到"p1所在链表的末尾"
            if(mVexs.get(p1).firstEdge == null)
                mVexs.get(p1).firstEdge = node1;
            else
                linkLast(mVexs.get(p1).firstEdge, node1);
        }
    }

    private void linkLast(ENode list, ENode node) {
        ENode p = list;

        while(p.nextEdge!=null)
            p = p.nextEdge;
        p.nextEdge = node;
    }

    private int getPosition(char ch) {
        for(int i=0; i<mVexs.size(); i++)
            if(mVexs.get(i).data==ch)
                return i;
        return -1;
    }

    public void print1() {
        System.out.printf("邻接表:\n");
        for (int i = 0; i < mVexs.size(); i++) {
            System.out.printf("V(%c): ",  mVexs.get(i).data);
            ENode node = mVexs.get(i).firstEdge;
            while (node != null) {
                System.out.printf("V(%c) ", mVexs.get(node.i).data);
                node = node.nextEdge;
            }
            System.out.printf("\n");
        }
    }
    public void print() {
        System.out.printf("邻接表:\n");
        for (int i = 0; i < mVexs.size(); i++) {
            System.out.printf("%c: ",  mVexs.get(i).data);
            ENode node = mVexs.get(i).firstEdge;
            while (node != null) {
                System.out.printf("%c ", mVexs.get(node.i).data);
                node = node.nextEdge;
            }
            System.out.printf("\n");
        }
    }
    public int TpSort() {
        int index = 0;
        int num = mVexs.size();
        int[] ins;               // 入度数组
        char[] tops;
        Queue<Integer> queue;

        ins   = new int[num];
        tops  = new char[num];
        queue = new LinkedList<Integer>();

        // 统计每个顶点的入度数
        for(int i = 0; i < num; i++) {

            ENode node = mVexs.get(i).firstEdge;
            while (node != null) {
                ins[node.i]++;
                node = node.nextEdge;
            }
        }

        // 将所有入度为0的顶点入队列
        for(int i = 0; i < num; i ++)
            if(ins[i] == 0)
                queue.offer(i);                 // 入队列

        while (!queue.isEmpty()) {              // 队列非空
            int j = queue.poll().intValue();    // 出队列。j是顶点的序号
            tops[index++] = mVexs.get(j).data;  // 将该顶点添加到tops中，tops是排序结果
            ENode node = mVexs.get(j).firstEdge;// 获取以该顶点为起点的出边队列
            while(node != null) {
                // 将节点(序号为node.i)的入度减1。
                ins[node.i]--;
                // 若节点的入度为0，则将其"入队列"
                if( ins[node.i] == 0)
                    queue.offer(node.i);    // 入队列

                node = node.nextEdge;
            }
        }

        if(index != num) {
            System.out.printf("有向有环图\n");
            return 1;
        }

        // 打印拓扑排序结果
        System.out.printf("拓扑排序: ");
        for(int i = 0; i < num; i ++)
            System.out.printf("%c ", tops[i]);
        System.out.printf("\n");

        return 0;
    }

    public static void main(String[] args) {
        Topo list;
        char[] l = {'1', '2', '3', '4', '5', '6'};
        char[][] point = new char[][]{
                {'1', '2'},
                {'1', '3'},
                {'2', '4'},
                {'2', '5'},
                {'3', '4'},
                {'3', '6'},
                {'5', '6'},
                {'4', '6'}
        };

        list = new Topo(l, point);
        list.print1();
        list.TpSort();     // 拓扑排序

    }
}
